#include <iostream>
#include "LinkList.hpp"

using namespace std;

template <class T>
class Stack
{
public:
    Node<T> *head;
    int length;

    Stack();
    ~Stack();
    void Emplace(const T &data);
    void Clear();
    T Pop();
    T Top();
};

template <class T>
Stack<T>::Stack()
{
    this->head = new Node<T>();
    this->head->next = nullptr;
    this->length = 0;
}

template <class T>
void Stack<T>::Emplace(const T &data)
{
    Node<T> *newNode = new Node<T>();
    newNode->data = data;
    newNode->next = this->head->next;
    this->head->next = newNode;
    this->length++;
}

template <class T>
T Stack<T>::Pop()
{
    T ret = this->head->next->data;
    Node<T> *p = this->head->next;
    this->head = p->next;
    delete p;
    this->length--;
    return ret;
}

template <class T>
T Stack<T>::Top()
{
    return this->head->next->data;
}

template <class T>
void Stack<T>::Clear()
{
    while (this->head->next != nullptr)
    {
        Node<T> *cur = this->head->next;
        this->head = cur->next;
        delete cur;
    }
    this->length = 0;
}

template <class T>
Stack<T>::~Stack()
{
    while (this->head != nullptr)
    {
        Node<T> *cur = this->head;
        this->head = cur->next;
        delete cur;
    }
    this->length = 0;
}